package ch9sorting;

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Chapter {

	static void bubbleSort(int[] arr) {
		for (int counter = 0; counter < arr.length - 1; counter++) { // Loop once for
																// each element
																// in the array.
			for (int index = 0; index < arr.length - 1 - counter; index++) { // Once for
																		// each
																		// element,
																		// minus
																		// the
																		// counter.
				if (arr[index] > arr[index + 1]) { // Test
													// if
													// need
													// a
													// swap
													// or
													// not.
					int temp = arr[index]; // These three lines just swap
													// the two elements:
					arr[index] = arr[index + 1];
					arr[index + 1] = temp;
				}
			}
		}
	}
	
	static int [] countingSort(Integer [] arr) {
		int [] b = new int [arr.length];
		int max = Collections.max(Arrays.asList(arr));
		int [] c = new int [max+1];
		
		for (int cindex : arr) {
			c[cindex] += 1;
		}
		
		for (int i=2; i<=max; i++) {
			c[i] += c[i-1];
		}
		
		for (int i=arr.length-1; i>=0; i--) {
			int cindex = arr[i];
			int bindex = c[cindex]-1;
			b[bindex] = arr[i];
			c[cindex]--;
		}
		return b;
	}

	public static void main(String ...strings) {
		Integer [] arr = {3,6,4,1,3,4,1,4};
		int[] countingSort = countingSort(arr);
		System.out.println(countingSort);
		Scanner scanner;
	}
	
}
